package io.github.maojian.dynamicprogramming;

/**
 * 粉刷房子2
 * 假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
 *
 * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。
 *
 * 例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。
 *
 * 所有花费均为正整数。
 *
 * 示例：
 *
 * 输入: [[1,5,3],[2,9,4]]
 * 输出: 5
 * 解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5;
 * 或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5.
 *
 * 要求：O(nk) 的时间复杂度下解决此问题
 */
public class Q265 {
    //先写一个nk2的
    //可能会出现只有一种颜色，那么这种特殊情况，肯定只有一个房子
    //然后如何从k2到k
    //有k个值，求除了i之外的最小值(i∈[1,k])
    //如果最小值是第i个元素，次小值是第j个元素
    //那么除了i之外的最小值是第j个元素
    //而除了其他的元素，最小值都是第i个元素
    //有趣，这时降为nk
    public int minCostII(int[][] costs) {
        if(costs==null || costs.length==0)return 0;
        if(costs[0].length==1) return costs[0][0];
        //创建dp数组并进行初始化
        int m = costs.length;
        int n = costs[0].length;
        int[][] dp = new int[m+1][n];
        //进行计算
        for(int i=1; i<=m; i++){//对于第i个房子
            int minValue = Integer.MAX_VALUE;
            int secMinValue = Integer.MAX_VALUE;
            int minIndex =-1;
            int secMinIndex = -1;
            for(int j=0; j<n; j++){//对于第j种颜色
                if(dp[i-1][j]<minValue){
                    secMinValue = minValue;
                    minValue = dp[i-1][j];
                    secMinIndex = minIndex;
                    minIndex = j;
                }
                else if(dp[i-1][j]<secMinValue){
                    secMinValue = dp[i-1][j];
                    secMinIndex = j;
                }
            }
            for(int j=0; j<n; j++){
                dp[i][j] = (j==minIndex?secMinValue:minValue) +costs[i-1][j];
            }
        }
        //返回最小值
        int res = Integer.MAX_VALUE;
        for(int k=0; k<n; k++){
            res = Math.min(res,dp[costs.length][k]);
        }
        return res;

    }
}
